#include <iostream>
#include <vector>
using namespace std;

void quickSort(vector<int>& v, int left, int right)
{
	if (left >= right) return;

	int i = left - 1, j = right + 1, key = v[rand() % (right - left + 1) + left];
	for (int cur = left; cur < j;)
	{
		if (v[cur] < key)
		{
			swap(v[cur++], v[++i]);
		}
		else if (v[cur] > key)
		{
			swap(v[cur], v[--j]);
		}
		else
		{
			++cur;
		}
	}

	quickSort(v, left, i);
	quickSort(v, j, right);
}
int main()
{
	srand(time(nullptr));

	vector<int> v = { 5,7,3,9,1,8,2,4,6 };
	quickSort(v, 0, v.size() - 1);

	for (auto& e : v)
	{
		cout << e << " ";
	}
	return 0;
}